package com.freedy.algorithm.greedy;

import java.util.*;

/**
 * @author Freedy
 * @date 2021/4/12 21:07
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //创建广播电台，放入到map
        HashMap<String, HashSet<String>> broadCasts = init();
        HashSet<String> allAreas = new HashSet<>();
        for (Map.Entry<String, HashSet<String>> entry : broadCasts.entrySet()) {
            allAreas.addAll(entry.getValue());
        }
        ArrayList<String> result = new ArrayList<>();
        while (!allAreas.isEmpty()){
            //每个电台覆盖了未覆盖的地区的电台的数量
            HashMap<String, Integer> selects = new HashMap<String, Integer>();
            for (Map.Entry<String, HashSet<String>> entry : broadCasts.entrySet()) {
                selects.put(entry.getKey(),0);
                for (String s : entry.getValue()) {
                    if (allAreas.contains(s)){
                        selects.merge(entry.getKey(),1,Integer::sum);
                    }
                }
            }
            int max=Integer.MIN_VALUE;
            String index="";
            //体现贪婪算法的特点
            for (Map.Entry<String, Integer> entry : selects.entrySet()) {
                if (entry.getValue()>max){
                    max=entry.getValue();
                    index=entry.getKey();
                }
            }
            HashSet<String> set = broadCasts.get(index);
            allAreas.removeAll(set);
            result.add(index);
        }
        System.out.println(result);
    }

    public static HashMap<String, HashSet<String>> init(){
        HashMap<String, HashSet<String>> broadCasts = new HashMap<>();
        HashSet<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");
        HashSet<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("深圳");
        HashSet<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");
        HashSet<String> set4 = new HashSet<>();
        set4.add("上海");
        set4.add("天津");
        HashSet<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");
        broadCasts.put("k1",set1);
        broadCasts.put("k2",set2);
        broadCasts.put("k3",set3);
        broadCasts.put("k4",set4);
        broadCasts.put("k5",set5);
        return broadCasts;
    }
}
